#define _CRT_SECURE_NO_WARNINGS 1

//class Solution {
//public:
//    bool checkDynasty(vector<int>& places) {
//        set<int> nums;
//        int count = 0;
//        for (int i : places)
//        {
//            if (i == 0)
//            {
//                count++;
//            }
//            else
//            {
//                nums.insert(i);
//            }
//        }
//
//        vector<int> n(nums.begin(), nums.end());
//        if ((nums.size() + count) != places.size())
//            return false;
//        int min = *n.begin();
//        min++;
//
//        for (int i = 1; i < n.size(); i++)
//        {
//            if (min != n[i] && count)
//            {
//                count--;
//                i--;
//            }
//            else if (min != n[i] && count == 0)
//            {
//                return false;
//            }
//            min++;
//        }
//        return true;
//    }
//};

//class Solution {
//public:
//    int trainWays(int num) {
//        if (num == 1 || num == 0)
//            return 1;
//        if (num == 2)
//            return 2;
//        long long int f1 = 1;
//        long long int f2 = 2;
//        long long int f3 = f1 + f2;
//        for (int i = 4; i <= num; i++)
//        {
//            f1 = f2;
//            f2 = f3 % 1000000007;
//            f3 = f1 + f2;
//        }
//        return f3 % 1000000007;
//    }
//};

//#include <algorithm>
//#include <iostream>
//#include <string>
//using namespace std;
//
//int main() {
//    long long int num;
//    cin >> num;
//    string str = to_string(num);
//    reverse(str.begin(), str.end());
//    int count = 0;
//    for (auto i = str.begin(); i != str.end(); i++)
//    {
//        count++;
//        if (count == 4)
//        {
//            str.insert(i, ',');
//            count = 0;
//        }
//    }
//    reverse(str.begin(), str.end());
//    cout << str;
//    return 0;
//}